Sprawy organizacyjne¶

  • Formuła zajęć: Wykład koleżeński, dyskusja;
  • Forma prezentacji: Omówienie wykładu/tematu pojawiającego się na kursie: http://cs229.stanford.edu/;
  • Forma prezentacji dowolna (proponuję trochę omówienia teoretycznego + przykłady metod w kodzie, wizualizacja);
  • Jak często prezentujemy - co tydzień;
  • Chętni mogą wrzucać swoje prezentacje do repo: https://github.com/lukaszlaszczuk/ml-gauss-summer-2021 ;
  • Skupiamy się na metodach, a nie na narzędziach;
  • Pytania, sugestie?

Rozkład zajęć¶

  1. Intro to ML, Linear Regression and Gradient Descent;
  2. Locally Weighted & Logistic Regression;
  3. Perceptron & Generalized Linear Model;
  4. GDA & Naive Bayes;
  5. Support Vector Machines;
  6. Kernels;
  7. Data Splits, Models & Cross-Validation;
  8. Approx/Estimation Error & ERM;
  1. Decision Trees and Ensemble Methods;
  2. Introduction to Neural Networks
  3. Backprop & Improving Neural Networks
  4. Debugging ML Models and Error Analysis
  5. Expectation-Maximization Algorithms
  6. Factor Analysis
  7. Independent Component Analysis & RL
  8. MDPs & Value/Policy Iteration
  9. Continuous State MDP & Model Simulation
  10. Reward Model & Linear Dynamical System
  11. RL Debugging and Diagnostics.

Plan na dziś¶

  • wstęp do uczenia maszynowego;
  • regresja liniowa;
  • gradient descent (metoda gradientu prostego, stochastyczny gradient prosty, minibatch gradient descent);

Co to jest uczenie maszynowe?¶

  • Arthur Samuel (1959) - "dziedzina nauki, która umożliwia uczenie komputerów bez konieczności ich programowania";
  • Tom M. Mitchell - "Mówimy, że program komputerowy uczy się ze skutecznością S zadania Z na podstawie doświadczenia D, jeśli jego skuteczność w wykonywaniu zadania Z rośnie wraz ze wzrostem doświadczenia D."

Interpretacja definicji Mitchella¶

Istotne aspekty przy realizowaniu projektu/zadania uczenia maszynowego:

  • Odpowiednie rozpoznanie zadania Z, tj. zrozumienie problemu biznesowego, infrastruktury/bazy danych klienta, odbiorcy końcowego, ... Czy uczenie maszynowe jest w ogóle potrzebne? rules of ml;
  • Zebranie odpowiedniego "doświadczenia" D, tj. danych. Integracja z infrastrukturą klienta czyszczenie danych, wizualizacja, transformacje danych, .... Jednym słowem wszystko, co może pozwolić na zwiększenie skuteczności (może stanowić najdłuższą część projektu);
  • Określenie sposobu mierzenia skuteczności S, np. dokładność, błąd średniokwadratowy, miara F1, ...

Rodzaje uczenia maszynowego¶

  • nadzorowane uczenie maszynowe (supervised ML);
  • nienadzorowane uczenie maszynowe (unsupervised ML);
  • uczenie maszynowe ze wzmocnieniem (reinforcement learning);
  • semi-supervised ML

Nadzorowane uczenie maszynowe¶

Dane: $(X, y)$, gdzie $X$ to zmienne wyjaśniające a $y$ to zmienna wyjaśniana;

Cel: Znaleźć optymalną funkcję przekształcającą $X$ w $y$.

  • Dwa typy problemów: regresja (gdy zmienna wyjaśniana jest ciągła), klasyfikacja (gdy zmienna wyjaśniana jest dyskretna);

  • Typy klasyfikacji: binarna (binary), wieloklasowa (multiclass), wieloetykietowa (multi-label). Przykłady?

title

Nienadzorowane uczenie maszynowe¶

Dane: $X$ - zbiór danych bez zmiennej wyjaśnianej;

Cel: Znaleźć "ciekawą" strukturę w danych.

Przykłady?

title

  • segmentacja rynku;
  • klastrowanie DNA;
  • systemy rekomendacyjne;
  • topic modeling;
  • detekcja anomalii;
  • social network analysis;
  • szukanie zmiany trendu.

Uczenie maszynowe ze wzmocnieniem¶

  • osadzamy "agenta" w pewnym otoczeniu i pozwalamy mu eksperymentować;
  • nagradzamy go za działania pozytywne oraz karzemy za działania negatywne w taki sposób, aby agent nauczył się wykonywać określone działania.

Przykłady?

title

Use-cases link

  • granie w gry (komputerowe, szachy, go);
  • autonomiczne samochody;
  • boty tradingowe;
  • optymalizacja zużycia energii (Google Data Center);
  • chatboty.

Semi-supervised learning¶

  • Używany w przypadku, gdy mamy ograniczony dostęp do wartości zmiennej wyjaśnianej;
  • Dzięki tego typu metodom możemy generować dane (zdjęcia, filmy, muzyka, ...) przykład

title

Regresja liniowa¶

Typowy przykład:

  • Estymacja ceny mieszkania na podstawie jego metrażu regresja

Schemat / Terminologia¶

schemat

  • Szukamy funkcji (hipotezy) $h$ minimalizującą pewną funkcję straty. Dla regresji liniowej $h(x) = \theta_0+\theta_1 x$.
  • $\theta$ - szukane parametry, minimalizujące pewną funkcję straty $J$;
  • $x$ - zmienne wyjaśniające;
  • $y$ - zmienna wyjaśniana;
  • $(x^{(i)},y^{(i)})$ - $i$-ta obserwacja ze zbioru treningowego.
  • $m$ - liczba obserwacji w zbiorze (rzędów);
  • $n$ - liczba zmiennych wyjaśniających (kolumn);
  • $J(\theta) = \displaystyle\frac{1}{2m}\sum_{i=1}^{m}\left(h(x^{(i)})-y^{(i)}\right)^2$

Metoda gradientu prostego¶

  • algorytm szukania minimów lokalnych funkcji (straty);
  • ma zastosowanie dla szerokiej gamy problemów;
  • istnieje kilka odmian algorytmu: wsadowa (batchowa), stochastyczna, minibatchowa.

gradient-desc

gradient-desc

Kroki algorytmu (wsadowy/batch gradient prosty)¶

  1. Wybierz początkowe $\theta$ (np. $\theta = \vec{0}$).
  2. Modyfikuj $\theta$, aby zminimalizować $J(\theta)$.
  3. $\theta_j:=\theta_j - \alpha\, \cfrac{\partial}{\partial \theta_j}\, J(\theta)$, gdzie $\alpha$ to współczynnik uczenia (learning rate), np. $\cfrac{\partial}{\partial \theta_j}\, J(\theta) = \cfrac{\partial}{\partial \theta_j}\cfrac{1}{2m}\displaystyle\sum_{i=1}^{m}\left(h_{\theta}(x^{(i)})-y^{(i)}\right)^2 = \ldots = \cfrac{1}{m}\displaystyle\sum_{i=1}^{m}(h_{\theta}(x^{(i)})-y^{(i)}) \, x_j$.
    Macierzowo możemy zapisać: $\cfrac{\partial}{\partial \theta_j}\, J(\theta) = \cfrac{1}{m} X^T \,(X\theta -y)$.
  4. Zaktualizuj $\theta_j$: $\theta_j:=\theta_j-\alpha \, \cfrac{1}{m}\displaystyle\sum_{i=1}^{m}(h_{\theta}(x^{(i)})-y^{(i)}) \, x_j$.
    Macierzowo: $\theta := \theta - \alpha \, \cfrac{1}{m}\,X^T \,(X\theta -y)$
  5. Powtarzaj kroki 1.-4. do momentu, aż błąd będzie wystarczająco niski lub osiągniemy maksymalny krok.

Implementacja¶

In [4]:
def loss_function(y_pred, y_real):
    return 1/2 * np.mean((y_pred-y_real)**2)

def batch_gradient_descent(theta,
                           X,
                           y,
                           n_iteration,
                           alpha,
                           theta_snapshot_rate=None):
    
    theta_snapshot_list = [[copy.deepcopy(theta), 0]]
    for iteration in range(n_iteration):
        theta = copy.deepcopy(theta)
        if iteration % theta_snapshot_rate == 0 and iteration!=0:
            append_list = [theta, iteration]
            theta_snapshot_list.append(append_list)
            
        gradient = np.mean(X.T.dot(X.dot(theta) - y), axis=1)
        gradient = np.reshape(gradient, (-1, 1))
        theta -= alpha * gradient     
        
    if len(theta_snapshot_list) > 0:
        return theta, theta_snapshot_list
    else:
        return theta

Przykłady: $\alpha=10^{-10}$¶

In [6]:
PlotUtil.plot_gradient_descent(df, 'GrLivArea', 'SalePrice', thetas_snapshot, alpha, 0, 6000, 0, 1000000)

Przykłady: $\alpha=10^{-9}$¶

In [8]:
PlotUtil.plot_gradient_descent(df, 'GrLivArea', 'SalePrice', thetas_snapshot, alpha, 0, 6000, -1000000, 10000000)

Przykłady: $\alpha=2\cdot10^{-15}$¶

In [10]:
PlotUtil.plot_gradient_descent(df, 'GrLivArea', 'SalePrice', thetas_snapshot, alpha, 0, 6000, 0, 1000000)

Kroki algorytmu (stochastyczny gradient prosty):¶

  • stosowany w przypadku, kiedy mamy duże dane i batchowy gradient descent jest wolny:
  1. Wybierz początkowe $\theta$ (np. $\theta = \vec{0}$).
  2. for i in range(m):
  3. Modyfikuj $\theta$, aby zminimalizować $J(\theta)$.
  4. Wybierz losową obserwację ze zbioru danych $(x^{(i)}, y^{(i)})$;
  5. $\theta_j:=\theta_j-\alpha \, (h_{\theta}(x^{(i)})-y^{(i)}) \, x_j$;
  6. Za $\alpha$ można przyjąć: $\cfrac{t_0}{(t+t_1)}$, gdzie $t_0$ i $t_1$ to wybrane współczynniki, a $t$ to number iteracji.
  7. Powtarzaj 2. - 6. ustaloną liczbę razy.
In [11]:
def learning_schedule(t, t0, t1):
    return t0/(t+t1)

def stoch_gradient_descent(theta,
                           X,
                           y,
                           n_iteration,
                           alpha=None,
                           learning_schedule=None,
                           t0=None,
                           t1=None,
                           theta_snapshot_rate=None):
    
    theta_snapshot_list = [[copy.deepcopy(theta), 0]]
    for iteration in range(n_iteration):
        theta = copy.deepcopy(theta)
        if iteration % theta_snapshot_rate == 0 and iteration != 0:
            append_list = [theta, iteration]
            theta_snapshot_list.append(append_list)
            
        for i in range(len(X)):
            rand_idx = np.random.randint(len(X))
            xi = X_b[rand_idx:rand_idx+1]
            yi = y[rand_idx:rand_idx+1]
            gradient = xi.T.dot(xi.dot(theta) - yi)
            if learning_schedule:
                alpha = learning_schedule(iteration*len(X)+i, t0, t1)
            theta -= alpha*gradient
        
    if len(theta_snapshot_list) > 0:
        return theta, theta_snapshot_list
    else:
        return theta

Przykłady:¶

In [12]:
n_iteration = 101
t0, t1 = 5, 5*10**8
theta_0 = np.zeros((2,1))
thetas_end, thetas_snapshot = stoch_gradient_descent(theta_0,
                                                    X_b,
                                                    y,
                                                    n_iteration,
                                                    learning_schedule=learning_schedule,
                                                    t0=t0,
                                                    t1=t1,
                                                    theta_snapshot_rate=1)
In [13]:
PlotUtil.plot_gradient_descent(df, 'GrLivArea', 'SalePrice', thetas_snapshot, (t0, t1), 0, 6000, 0, 1000000, "t0, t1:")
In [14]:
n_iteration = 101
alpha = 10**-10
theta_0 = np.zeros((2,1))
thetas_end, thetas_snapshot = stoch_gradient_descent(theta_0,
                                                    X_b,
                                                    y,
                                                    n_iteration,
                                                    alpha=alpha,
                                                    theta_snapshot_rate=1)
In [15]:
PlotUtil.plot_gradient_descent(df, 'GrLivArea', 'SalePrice', thetas_snapshot, alpha, 0, 6000, 0, 1000000)